package com.LeetCode.String;

import org.junit.Test;

import java.util.*;

/**
 * 回文对
 */
public class PalindromePairs {

    public List<List<Integer>> palindromePairs(String[] words) {
        HashMap<String, Integer> indexMap = new HashMap<>();

        HashSet<List<Integer>> set = new HashSet<>();

        HashMap<String, Integer> palindStrMap = new HashMap<>();
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < words.length; i++) {
            indexMap.put(words[i], i);
            if(new StringBuilder(words[i]).reverse().toString().equals(words[i])){
                palindStrMap.put(words[i],i);
            }
        }

        for (int i = 0; i < words.length; i++) {
            if(words[i].equals("")){
                for(String str : palindStrMap.keySet()){
                    if(i != palindStrMap.get(str)){
                        set.add(new ArrayList<>(Arrays.asList(i, palindStrMap.get(str))));
                        set.add(new ArrayList<>(Arrays.asList(palindStrMap.get(str), i)));
                    }
                }
            }else{
                String palindStr = new StringBuilder(words[i]).reverse().toString();
                if(indexMap.get(palindStr) != null && i != indexMap.get(palindStr)){
                    set.add(new ArrayList<>(Arrays.asList(i, indexMap.get(palindStr))));
                    set.add(new ArrayList<>(Arrays.asList(indexMap.get(palindStr), i)));
                }

                for(int j = 0; j<words[i].length(); j++){
                    String reverseRightStr = new StringBuilder(words[i].substring(j+1)).reverse().toString();
                    if(isPalindStr(words[i].substring(0,j+1)) && indexMap.get(reverseRightStr) != null
                        && i != indexMap.get(reverseRightStr)){
                        set.add(new ArrayList<>(Arrays.asList(indexMap.get(reverseRightStr), i)));
                    }
                }
                for(int j = words[i].length()-1; j>=0; j--){
                    String reverseLeftStr = new StringBuilder(words[i].substring(0,j+1)).reverse().toString();
                    if(isPalindStr(words[i].substring(j+1)) && indexMap.get(reverseLeftStr) != null
                        && i != indexMap.get(reverseLeftStr)){
                        set.add(new ArrayList<>(Arrays.asList(i, indexMap.get(reverseLeftStr))));
                    }
                }

            }
        }
        res.addAll(set);
        return res;
    }

    public boolean isPalindStr(String str){
        return str.equals(new StringBuilder(str).reverse().toString());
    }

    @Test
    public void test(){
        String[] words1 = {"abcd","dcba","lls","s","sssll"};
        String[] words2 = {"bat","tab","cat"};
        String[] words3 = {"ab","ba","abc","cba"};
        palindromePairs(words3).forEach(System.out::println);
//        System.out.println("abc".substring(0,1) + "" + "abc".substring(1));
    }
}
